Search for: All records

Collaborative text editing applications like Google docs, Etherpad and Overleaf allow users to con- currently edit a “shared” document. Most existing collab- orative text editing software require total ordering on the updates made to the document, which is achieved using a centralized sever or some form of consensus algorithm. Then on top of the ordering, the editor uses either opera- tional transformation (OT) or differential synchronization (diff-sync) to apply the ordered update events to the already committed changes on their local copies. If there is no delay or failure, then eventually all updates can be applied correctly in the agreed order. Unfortunately, not only are these methods computation- ally intensive but they often result in conflicts due to users writing to the same location. It has also been proved that the metadata overhead for such protocols are at least linear in the number of delete events. Moreover, these event- based and diff-based algorithms are exceptionally difficult to implement and there are no provably correct solutions to these problems in the face of heavy concurrency. These collaborative editors either provide no proven guarantees or only provide eventual guarantees for correctness. With LiteDoc, we propose a different approach to tackle this problem: we make collaborative editing fast, scalable and robust by providing simplified semantics. More im- portantly, we can formally prove that LiteDoc achieves deterministic guarantees of correctness. LiteDoc divides the shared document into several sections and allow only one user to write at a particular section at any given time. This removes all conflicts that arise from having multiple writers writing to the same location. This mechanism also obviates the task of implementing cumbersome modules for OT, diff-sync and rollbacks in case of conflicts. Note that while LiteDoc supports less features than general collaborative editors like Google docs, it is natural (and courteous) to avoid concurrent writing to the same location when multiple people collaborate.